﻿//给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
//
//struct Node {
//	int val;
//	Node *left;
//	Node *right;
//	Node *next;
//}
//填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
//
//初始状态下，所有 next 指针都被设置为 NULL。


class Solution {
public:
	Node* connect(Node* root)
	{
		if (root == nullptr)
		{
			return root;
		}
		Node* leftnode = root;
		while (leftnode->left != nullptr)
		{
			Node* head = leftnode;
			while (head)
			{
				head->left->next = head->right;
				if (head->next)
				{
					head->right->next = head->next->left;
				}
				head = head->next;
			}
			leftnode = leftnode->left;
		}
		return root;
	}
	/*Node* connect(Node* root) {
	if(root==nullptr)
	{
	return root;
	}
	queue<Node*> q;
	q.push(root);
	while(!q.empty())
	{
	int size=q.size();
	for(int i=0;i<size;i++)
	{
	Node* node=q.front();
	q.pop();
	if(i!=size-1)
	{
	node->next=q.front();
	}
	if(node->left)
	{
	q.push(node->left);
	}
	if(node->right)
	{
	q.push(node->right);
	}
	}
	}
	return root;
	}
	*/
};

